0% completed
Logarithmic Time Complexity
Key Characteristics
In an algorithm with
-
Time Complexity: The runtime grows logarithmically as the input size increases, due to dividing the problem in each step.
-
Space Complexity: The memory usage grows logarithmically with the input size due to the depth of the recursive call stack.
Code Example
Here’s a recursive example that demonstrates n, by repeatedly halving n.
- Explanation: This function keeps dividing
nby 2 untilnbecomes 1 or less, adding 1 to the count at each step.
Analyzing the Time Complexity Using Recurrence Relation
To understand the time complexity, let’s set up a recurrence relation for the function:
Step 1: Define the Recurrence Relation
- Let
represent the time complexity of largest_power_of_twofor an input of sizen. - Each time we call
largest_power_of_two(n // 2), we halven, so we can express the time complexity as:
Here:
represents the recursive call with input size halved. represents the constant work done in each recursive step (the addition).
Step 2: Solve the Recurrence Relation
- Let’s expand this recurrence relation step by step to understand the total number of recursive calls.
- The process continues until the input size is reduced to 1, at which point the function stops. This happens when
, which simplifies to:
- Taking the logarithm of both sides, we get:
- So,
because there are recursive calls before reaching the base case.
Analyzing Space Complexity Using Recurrence Relation
The space complexity also grows logarithmically because each recursive call uses a stack frame, and the maximum number of stack frames corresponds to the depth of recursion.
- Define the Space Recurrence Relation:
- Let
represent the space complexity. - Each recursive call adds one frame to the call stack, and the stack grows as the input is halved:
- Let
- Recursive Depth and Space Complexity:
- Similar to the time complexity, the recursion depth reaches
. - Therefore, the space complexity is also:
- Similar to the time complexity, the recursion depth reaches
On this page
Key Characteristics
Code Example
Analyzing the Time Complexity Using Recurrence Relation
Analyzing Space Complexity Using Recurrence Relation